package org.cainiao.algorithm.greedy;

import java.util.HashSet;

/**
 * <br />
 * <p>
 * Author: Cai Niao(wdhlzd@163.com)<br />
 */
public class MinLight {

    public static int minLightViolent(String road) {
        if (road == null || road.length() == 0) {
            return 0;
        }
        return process(road.toCharArray(), 0, new HashSet<>());
    }

    /**
     * 递归的含义：
     * 0 ~ index - 1 放灯位置确定的情况下
     * 在 index ~ str.length -1 点灯位置的所有排列组合中
     * 点亮 str 中所有需要点亮的位置，至少需要多少盏灯
     * 在这种情况下无法点亮所有位置的灯，则返回 Integer.MAX_VALUE
     * <p>
     * 分步
     * 每一步按顺序消费一个数组元素
     * 每一步有 2 种选择：点灯、不点灯
     * 恢复现场：调用 process() 前后，lights 不变
     *
     * @param str    字符数组
     * @param index  当前位置
     * @param lights 0 到 index - 1 放灯索引的集合
     * @return 在 0 到 index - 1 的放灯方式已确定的前提下，要照亮所有的 '.'，最少需要多少盏灯
     * -        做子递归之前不保证 0 到 index - 1 的放灯方式能照亮所有的 '.'
     * -        但子递归遇到边界时会将没有照亮所有 . 的情况赋值为 Integer.MAX_VALUE，从而在比较中被淘汰
     */
    public static int process(char[] str, int index, HashSet<Integer> lights) {
        if (index == str.length) {
            /*
             * 所有位置的放灯方式都已确定
             * 看看是不是所有的 '.' 都被照亮了
             * 如果是，则返回放灯的数量
             * 如果不是，则返回 Integer.MAX_VALUE（最大 int 值，为了让它在比较时被淘汰）
             */
            for (int i = 0; i < str.length; i++) {
                if (str[i] != 'X') {
                    if (!lights.contains(i - 1)
                        && !lights.contains(i)
                        && !lights.contains(i + 1)) {
                        return Integer.MAX_VALUE;
                    }
                }
            }
            return lights.size();
        }
        // 当前位置不放灯
        int no = process(str, index + 1, lights);
        // 当前位置放灯
        int yes = Integer.MAX_VALUE;
        if (str[index] == '.') {
            lights.add(index);
            yes = process(str, index + 1, lights);
            lights.remove(index);
        }
        /*
         * 如果当前位置为 X，则当前位置放灯的情况应该被舍弃，因为是题目不允许的
         * 这种情况 yes = Integer.MAX_VALUE，会被下边的 Math.min() 方法淘汰掉
         */
        return Math.min(no, yes);
    }

    /**
     * 遍历字符数组
     * 遇到 X，跳过
     * 遇到 .，点灯数加 1，然后判断下 1 个位置（这个点灯数 加 1 只是计数，不代表是在当前位置点灯，有可能是为下一个位置点灯计数）
     * -  如果下 1 个位置等于 length，则跳出循环
     * -  如果下 1 个位置是 X，则 index + 2，跳过它
     * -  如果下 1 个位置是 .，则 index + 3，跳过两个位置
     * -      (.).X(.)，下 2 个位置如果是 X，不需要点灯，可以跳过
     * -      (.)..(.)，下 2 个位置是 .，下 3 个位置是 .，则在下 3 个位置点灯可照亮下 2 位置
     * -      .(.).X 或 .(.).，如果下 1、2 个位置是 .，下 3 个位置是 X 或数组越界，则应该在下 1 个位置点灯，本次计数可看作是为下 1 个位置计的数
     */
    public static int minLightGreedy(String road) {
        if (road == null || road.length() == 0) {
            return 0;
        }
        char[] str = road.toCharArray();
        int length = str.length;
        int light = 0;
        int index = 0;
        while (index < length) {
            if (str[index] == 'X') {
                index++;
                continue;
            }
            light++;
            if (index + 1 == length) {
                break;
            }
            index += str[index + 1] == 'X' ? 2 : 3;
        }
        return light;
    }

    public static void main(String[] args) {
        test("....");
        test("...X");
        test(".X...");

        System.out.println("ans1 vs ans2");
        int len = 20;
        int testTime = 100000;
        for (int i = 0; i < testTime; i++) {
            String test = randomString(len);
            int ans1 = minLightViolent(test);
            int ans2 = minLightGreedy(test);
            if (ans1 != ans2) {
                System.out.println("oops!");
            }
        }
        System.out.println("finish!");
    }

    private static void test(String str) {
        System.out.println(str);
        int x = minLightViolent(str);
        int y = minLightGreedy(str);
        if (x != y) {
            System.out.println("oops!");
        }
        System.out.println(x);
        System.out.println(y);
        System.out.println();
    }

    public static String randomString(int len) {
        char[] res = new char[(int) (Math.random() * len) + 1];
        for (int i = 0; i < res.length; i++) {
            res[i] = Math.random() < 0.5 ? 'X' : '.';
        }
        return String.valueOf(res);
    }
}
